﻿using System;

namespace Activity.V
{
	/// <summary>
	/// Узел бинарного сбалансированного дерева.
	/// </summary>
	public class AVLNode
	{
		/// <summary>
		/// Получить глубину указанного узла относительно его корня.
		/// </summary>
		/// <param name="node">Узел для которого необходимо узнать глубину.</param>
		/// <returns>Возвращает глубину указанного узла.</returns>
		public static int GetDepth(AVLNode node)
		{
			var retVal = 0;
			// Инструментируем значение глубины до тех пор пока имеются родительские узлы 
			while ((node = node.Parent) != null) retVal++;
			return retVal;
		}

		/// <summary>
		/// Рекурсивно посчитать высоту дерева относительно указанного узла.
		/// </summary>
		public static int GetMaxHeight(AVLNode node)
		{
			if (node == null) return 0;
			return 1 + Math.Max(GetMaxHeight(node.left), GetMaxHeight(node.right));
		}

		/// <summary>
		/// Получить значение свойства Height из указанного узла.
		/// </summary>
		/// <returns>Возвращает высоту узла если удалось получить свойство, в противном случае -1.</returns>
		public static int GetHeightValue(AVLNode node)
		{
			return node != null ? node.Height : -1;
		}

		protected AVLNode right;
		protected AVLNode left;
		protected AVLNode parent;

		/// <summary>
		/// Значение узла.
		/// </summary>
		public object Value { get; set; }

		/// <summary>
		/// Левая ветка [значение меньше текущего].
		/// </summary>
		public AVLNode Left { get { return left; } set { left = value; } }

		/// <summary>
		/// Правая ветка [значение больше текущего].
		/// </summary>
		public AVLNode Right { get { return right; } set { right = value; } }

		/// <summary>
		/// Родительский узел к которому прикрепленный данный узел. 
		/// </summary>
		public AVLNode Parent { get { return parent; } set { parent = value; } }

		/// <summary>
		/// Высота узла относительно корня.
		/// </summary>
		public int Height { get; private set; }

		/// <summary>
		/// Располагается ли данный элемент на левой ветке своего родителя.
		/// </summary>
		public bool IsLeft { get { return Parent != null && Parent.Left == this; } }

		/// <summary>
		/// Располагается ли данный элемент на правой ветке своего родителя.
		/// </summary>
		public bool IsRight { get { return Parent != null && Parent.Right == this; } }

		/// <summary>
		/// Пересчитать высоту узла опираясь на значения его дочерних узлов.
		/// </summary>
		internal void FixHeight()
		{
			Height = Math.Max(GetHeightValue(left), GetHeightValue(right)) + 1;
		}
	}
}
